package 力扣日常刷题.木22一月.第14天0123;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 帅小伙
 * @date 2022/1/23
 * @description
 *   类似最长上升子序列    找到最大连接
 */
public class Demo53动态规划最长斐波那契数列 {


    public int lenLongestFibSubseq(int[] arr) {
        int N = arr.length;
        Map<Integer, Integer> index = new HashMap<Integer, Integer>();
        for (int i = 0; i < N; i++) {
            index.put(arr[i],i);
        }
        Map<Integer, Integer> longest = new HashMap<>();
        int ans = 0;
        for (int k = 0; k < N; k++) {
            for (int j = 0; j < k; j++) {
                int i = index.getOrDefault(arr[k] -  arr[j],-1);
                if(i >= 0 && i < j){
                    // i---j   存成  i*N + j
                    int cand = longest.getOrDefault(i*N+j,2)+1;
                    longest.put(j*N+k,cand);
                    ans = Math.max(ans,cand);
                }
            }
        }
        return N > 2 ? ans : 0;
    }
}
